package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC931 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minFallingPathSum(int[][] matrix) {
            int n = matrix.length;
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }

            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int curAns = dfs(0, i, matrix, dp);
                ans = Math.min(ans, curAns);
            }

            return ans;
        }

        /**
         * 当前已经在i,j 位置，求当前i,j 位置的走完后的最小结果
         *
         * @param i
         * @param j
         * @param dp
         * @return
         */
        public int dfs(int i, int j, int[][] matrix, int[][] dp) {
            if (Integer.MAX_VALUE != dp[i][j]) return dp[i][j];
            if (i == matrix.length - 1) return matrix[i][j];

            int left = Integer.MAX_VALUE, down = Integer.MAX_VALUE, right = Integer.MAX_VALUE, ans = Integer.MAX_VALUE;
            if (j - 1 >= 0) left = matrix[i][j] + dfs(i + 1, j - 1, matrix, dp);
            down = matrix[i][j] + dfs(i + 1, j, matrix, dp);
            if (j + 1 <= matrix.length - 1) right = matrix[i][j] + dfs(i + 1, j + 1, matrix, dp);
            ans = Math.min(left, down);
            ans = Math.min(ans, right);
            dp[i][j] = ans;
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();

//        输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
//        输出：13
//        解释：下面是两条和最小的下降路径，用加粗+斜体标注：
//[[2,1,3],      [[2,1,3],
// [6,5,4],       [6,5,4],
// [7,8,9]]       [7,8,9]]

        System.out.println(solution.minFallingPathSum(InputUtil.toDoubleIntegerArray("[[2,1,3],[6,5,4],[7,8,9]]")));

//        示例 2：
//
//        输入：matrix = [[-19,57],[-40,-5]]
//        输出：-59
//        解释：下面是一条和最小的下降路径，用加粗+斜体标注：
//[[-19,57],
// [-40,-5]]
        System.out.println(solution.minFallingPathSum(InputUtil.toDoubleIntegerArray("[[-19,57],[-40,-5]]")));


        System.out.println(solution.minFallingPathSum(InputUtil.toDoubleIntegerArray("[[-48]]")));
    }

    public static void main(String[] args) throws Exception {
        LC931 an = new LC931();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
